import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class question_39 {
}
class Solution_39 {
    //    思路是采用dfs的方法
    public void dfs(int arr[], int target, List<List<Integer>> result, List<Integer> temp,int start){

        for (int i = start; i < arr.length; i++) {
            if(arr[i]==target){
                temp.add(arr[i]);
                result.add(new ArrayList<Integer>(temp));
//                这个时候说明已经是等于了，那么就不再需要往下递归和往右边遍历了，因为往右边只会变得更大，因为是有序数组来的
                temp.remove(temp.size()-1);
                return;
            } else if (arr[i]>target) {
//                这个时候说明已经是大于了，那么就不再需要往下递归和往右边遍历了，因为往右边只会变得更大，因为是有序数组来的
                return;
            }else {
//                小于，还得接着递归
                temp.add(arr[i]);
                dfs(arr,target-arr[i],result,temp,i);
//                dfs之后记得还原,也就是吧刚刚添加的那个值删掉
                temp.remove(temp.size()-1);
            }
        }
        return;

    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        默认是从小到大排序的
        Arrays.sort(candidates);
        List<List<Integer>> result=new ArrayList<>();
        dfs(candidates,target,result,new ArrayList<Integer>(),0);
        return result;
    }
////    思路是采用dfs的方法
//    public void dfs(int arr[],int target,List<List<Integer>> result,int[] temp,int index,int start){
////        进来之前先把temp数组在index前面的数值全部加一遍
//        int sum=0;
//        for (int i = 0; i < index; i++) {
//            sum+=temp[i];
//        }
//        for (int i = start; i < arr.length; i++) {
//            if(sum+arr[i]==target){
//                List<Integer> list=new ArrayList<>();
//                temp[index]=arr[i];
//                for (int j = 0; j <= index; j++) {
//                    list.add(temp[j]);
//                }
//                result.add(list);
////                这个时候说明已经是等于了，那么就不再需要往下递归和往右边遍历了，因为往右边只会变得更大，因为是有序数组来的
//                return;
//            } else if (sum+arr[i]>target) {
////                这个时候说明已经是大于了，那么就不再需要往下递归和往右边遍历了，因为往右边只会变得更大，因为是有序数组来的
//                return;
//            }else {
////                小于，还得接着递归
//                temp[index]=arr[i];
//                dfs(arr,target,result,temp,index+1,i);
//            }
//        }
//        return;
//
//    }
//    public List<List<Integer>> combinationSum(int[] candidates, int target) {
////        默认是从小到大排序的
//        Arrays.sort(candidates);
//        int len=target/candidates[0];
//        List<List<Integer>> result=new ArrayList<>();
//        int temp[]=new int[len];
//        dfs(candidates,target,result,temp,0,0);
//        return result;
//    }
}
